package helper.base.math

object DBMHelper {
    class IntMatrix(
        val matrix: Array<Array<Int?>>,
    ) {
        companion object {
            fun makeIntMatrix(
                matrix: Array<Array<Int?>>,
            ): IntMatrix {
                return IntMatrix(matrix)
            }

            fun makeIntMatrix(
                vararg rows: Array<Int?>,
                unused: Boolean = true,
            ): IntMatrix {
                return IntMatrix(arrayOf(*rows))
            }

            fun makeIntMatrix(
                rows: Int,
                cols: Int,
                initialValue: Int? = null,
            ): IntMatrix {
                val matrix = Array(rows) { Array<Int?>(cols) { initialValue } }
                return IntMatrix(matrix)
            }

            fun makeSquareIntMatrix(
                size: Int,
                initialValue: Int? = null,
            ): IntMatrix {
                return makeIntMatrix(size, size, initialValue)
            }
        }

        val rows: Int
            get() = matrix.size

        val cols: Int
            get() = if (matrix.isNotEmpty()) matrix[0].size else 0

        fun floydWarshall(): Pair<IntMatrix, Int?> {
            val numVertices = rows
            val dist = makeSquareIntMatrix(numVertices, null)
            var firstNegativeCycleVertex: Int? = null
            // 初始化距离矩阵
            for (i in 0 until numVertices) {
                for (j in 0 until numVertices) {
                    if (i == j) {
                        dist.matrix[i][j] = 0
                    } else if (matrix[i][j] != null) {
                        dist.matrix[i][j] = matrix[i][j]
                    }
                }
            }

            // 弗洛伊德-沃肖尔算法
            println("弗洛伊德-沃肖尔算法:")
            for (k in 0 until numVertices) {
                println("k=${k}:")
                for (i in 0 until numVertices) {
                    for (j in 0 until numVertices) {
                        val ik = dist.matrix[i][k]
                        val kj = dist.matrix[k][j]
                        val ij = dist.matrix[i][j]
                        if (ik != null && kj != null && (ij == null || ik + kj < ij)) {
                            dist.matrix[i][j] = ik + kj
                            if (i == j && dist.matrix[i][j]!! < 0) {
                                // 检查负权重循环
                                firstNegativeCycleVertex = i
                                break
                            }
                        }
                    }
                    if (firstNegativeCycleVertex != null) break
                }
                dist.printMatrix()
                if (firstNegativeCycleVertex != null) break
            }

            return Pair(dist, firstNegativeCycleVertex)
        }

        fun printMatrix() {
            val separator = "-".repeat(32)

            // 打印头部分割线
            println(separator)

            // 打印行和列的数量
            println("Rows: ${rows}, Cols: $cols")

            // 打印矩阵内容
            println("Matrix:")
            for (row in matrix) {
                println(row.joinToString(" ") { it?.let { "%4d".format(it) } ?: " INF" })
            }

            // 打印尾部分割线
            println(separator)
        }

        object UnitTest {
            object PrintTest {
                fun test_33() {
                    val squareMatrix = makeSquareIntMatrix(3, 2)
                    squareMatrix.printMatrix()
                }

                fun test_34() {
                    val intMatrix = makeIntMatrix(3, 4, 1)
                    intMatrix.printMatrix()
                }

                @JvmStatic
                fun main(args: Array<String>) {
                    test_33()
                    test_34()
                }
            }

            object FloydWarshallTest {
                fun t1() {
                    val intMatrix = makeSquareIntMatrix(4, 0)

                    val (shortestPaths, firstNegativeCycleVertex) = intMatrix.floydWarshall()

                    if (firstNegativeCycleVertex != null) {
                        println("图中存在负权重循环，首个涉及顶点: $firstNegativeCycleVertex")
                    } else {
                        println("图中不存在负权重循环。")
                    }
                    shortestPaths.printMatrix()
                }

                fun t2() {
                    val intMatrix = makeIntMatrix(
                        arrayOf(0, 4, null),
                        arrayOf(null, 0, -2),
                        arrayOf(-3, null, 0),
                    )
                    intMatrix.printMatrix()

                    val (shortestPaths, firstNegativeCycleVertex) = intMatrix.floydWarshall()

                    if (firstNegativeCycleVertex != null) {
                        println("图中存在负权重循环，首个涉及顶点: $firstNegativeCycleVertex")
                    } else {
                        println("图中不存在负权重循环。")
                    }
                    shortestPaths.printMatrix()
                }

                @JvmStatic
                fun main(args: Array<String>) {
                    t2()
                }
            }
        }
    }
}
